package m202405.d12;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/5/12 11:32
 */
public class Q76 {

    public static void main(String[] args) {
        Q76 q76 = new Q76();
        q76.minWindow("ADOBECODEBANC", "ABC");
    }

    public String minWindow(String s, String t) {
        Map<Character, Integer> tWindow = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            Integer orDefault = tWindow.getOrDefault(c, 0);
            tWindow.put(c, orDefault + 1);
        }
        Map<Character, Integer> c = new HashMap<>();
        int rl = -1;
        int rr = -1;
        int left = 0;
        int right = 0;
        boolean flag = false;
        while (true) {
            boolean contains = contains(c, tWindow);
            if (contains) {
                Integer integer = c.get(s.charAt(left));
                if (integer == 1) {
                    c.remove(s.charAt(left));
                } else {
                    c.put(s.charAt(left), integer - 1);
                }
                left++;
                flag = true;
            } else {
                if (flag) {
                    if (rr == -1) {
                        rr = right;
                        rl = left - 1;
                    } else {
                        if (right - left + 1 < rr - rl) {
                            rr = right;
                            rl = left-1;
                        }
                    }
                    flag = false;
                }
                if (right >= s.length()) {
                    break;
                }
                c.put(s.charAt(right), c.getOrDefault(s.charAt(right), 0) + 1);
                right++;
            }
        }
        if (rr == -1) {
            return "";
        }
        return s.substring(rl, rr);
    }

    private boolean contains(Map<Character, Integer> c, Map<Character, Integer> t) {
        for (Character character : t.keySet()) {
            Integer orDefault = c.getOrDefault(character, 0);
            if (orDefault < t.get(character)) {
                return false;
            }
        }
        return true;
    }
}
